package 分类.回溯;

import java.util.LinkedList;
import java.util.List;

public class 括号生成 {
    static List<String> res=new LinkedList<>();
    static StringBuilder bs=new StringBuilder();
    public static List<String> generateParenthesis(int n) {
        back(n,n,n);
        return res;
    }

    static void back(int left,int right,int n){
        if(left<0||right<0||left>right){
            return;
        }
        if(bs.length()==2*n){
            res.add(bs.toString());
        }
        bs.append('(');
        back(left-1,right,n);
        bs.deleteCharAt(bs.length()-1);
        bs.append(')');
        back(left,right-1,n);
        bs.deleteCharAt(bs.length()-1);
    }

    public static void main(String[] args) {
        List<String> res=generateParenthesis(5);
        for (String re : res) {
            System.out.println(re);
        }
    }
}
